// https://leetcode.cn/problems/n-th-tribonacci-number/

// 算法思路总结：
// 1. 使用动态规划或迭代法求解泰波那契数列
// 2. 维护前三个值的状态变量进行迭代计算
// 3. 处理n=0,1,2的特殊边界情况
// 4. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int tribonacci(int n) 
    {
        vector<int> dp(n + 1);
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;

        int a = 0, b = 1, c = 1;
        int d = 0;
        for (int i = 3 ; i <= n ; i++)
        {
            d = c + b + a;
            a = b;
            b = c;
            c = d;
        }

        return d;
    }
};  

int main()
{
    int n1 = 4, n2 = 25;
    Solution sol;

    cout << sol.tribonacci(n1) << endl;
    cout << sol.tribonacci(n2) << endl;

    return 0;
}